package 简单算法;

import java.util.Arrays;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019-05-22
 * @Description: 合并两个排序的整数数组A和B变成一个新的数组。
 * 样例
 * 样例 1:
 * 输入：[1, 2, 3]  3  [4,5]  2
 * 输出：[1,2,3,4,5]
 * 解释:
 * 经过合并新的数组为[1,2,3,4,5]
 * 样例 2:
 * 输入：[1,2,5] 3 [3,4] 2
 * 输出：[1,2,3,4,5]
 * 解释：
 * 经过合并新的数组为[1,2,3,4,5]
 * 注意事项
 * 你可以假设A具有足够的空间（A数组的大小大于或等于m+n）去添加B中的元素。
 * 分析:涉及两个有序数组合并,设置i和j双指针,分别从两个数组的尾部想头部移动,并判断A[i]和B[j]的大小关系,从而保证最终数组有序,同时每次index从尾部向头部移动。
 **/
public class 合并排序数组 {

    public static void main(String[] args) {
        合并排序数组 s = new 合并排序数组();
        s.mergeSortedArray(new int[]{1, 2, 5}, 3, new int[]{3, 4}, 2);
    }

    public void mergeSortedArray(int[] A, int m, int[] B, int n) {
        // write your code here

        int i = m - 1, j = n - 1, index = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (A[i] > B[j]) {
                A[index--] = A[i--];
            } else {
                A[index--] = B[j--];
            }
        }


        while (i>=0){
            A[index--] = A[i--];
        }

        while (j>=0){
            A[index--] = B[j--];
        }

//        int[] c = Arrays.copyOf(A, A.length);
//        A = new int[m + n];
//        int ai = 0;
//        int bi = 0;
//        int index = 0;
//        //先将两个数组进行比较，排序放到新的数组中去
//        while (ai < m && bi < n) {
//            if (c[ai] < B[bi]) {
//                A[index++] = c[ai++];
//            } else {
//                A[index++] = B[bi++];
//            }
//        }
//
//        //将数组A的数据移到新的数组
//        while (ai < m) {
//            A[index++] = c[ai++];
//        }
//
//        //将数组B的数据移到新的数组
//        while (bi < n) {
//            A[index++] = B[bi++];
//        }

    }
}
